// 搜索插入的位置
// 给定一个排序数组和一个目标值
// 1. 在数组中找到目标值，并返回其索引。
// 2. 如果目标值不存在于数组中，返回它将会被顺序插入的位置。

/**
 * 1. 循环遍历
 * 数组的每个值都与目标值进行比较
 *  - 如果当前值等于目标值，则返回当前值索引
 *  - 如果当前值大于目标值，则需要插入到当前位置对应的索引处，
 *    返回当前值对应的索引
 */
// function searchInsert1(array, target) {
//     for (let index = 0; index < array.length; index++){
//         const element = array[index];
//         if (element >= target) {
//             return index;
//         }
//     }
//     return array.length;
// }
// const arr = [1,3,7,9,11];
// const r1 = searchInsert1(arr, 5);
// console.log('r1: ', r1);
// const r2 = searchInsert1(arr, 3);
// console.log('r2: ',r2);
// const r3 = searchInsert1(arr, 7);
// console.log('r3: ',r3);

/**
 * 2. 二分查找
 *  (1) 取left和right, 表示左右两个索引
 *  (2) 取中间索引对应的值, 和目标值进行比较
 *    - 中间值等于目标值, 则返回中间值对应的索引
 *    - 中间值小于目标值, 则修改left索引, 继续寻找
 *    - 中间值大于目标值, 则修改right索引, 继续寻找
 *  (3) 如果没有找到目标值，则直接返回left索引
 *  o(logn)
 */
function searchInsert2(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
const arr = [1,3,7,9,11];
const r1 = searchInsert2(arr, 5);
console.log('r1: ', r1);
const r2 = searchInsert2(arr, 3);
console.log('r2: ',r2);
const r3 = searchInsert2(arr, 7);
console.log('r3: ',r3);